/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package org.osdtsystem.dataset;

import java.util.AbstractCollection;
import java.util.ArrayList;
import java.util.List;
import java.util.NoSuchElementException;

/**
 * A subset of a data set.
 * @author Matthias Buch-Kromann
 */
public class DatasetSubset extends AbstractCollection<Integer> implements Dataset {
    private final DatasetRaw baseDataset;
    private final int[] identifiers;
    private double totalWeight;

    DatasetSubset(double totalWeight, Dataset dataset, int... identifiers) {
        this.baseDataset = dataset.baseDataSet();
        this.identifiers = identifiers;
        this.totalWeight = totalWeight;
    }

    /**
     * Constructor for a subset of a dataset with the identifiers given as a list.
     * @param dataset the parent dataset
     * @param identifierList the identifiers in the subset as a list
     */
    public DatasetSubset(Dataset dataset, List<Integer> identifierList) {
        this( 0,dataset.baseDataSet(), new int[identifierList.size()]);

        // Store list in identifiers
        for (int i = 0; i < identifiers.length; ++i) {
            identifiers[i] = identifierList.get(i);
        }

        // Recalculate weight
        recalculateWeight();
    }

    /**
     * Constructor for a subset of a dataset with the identifiers given as
     * an array of integers.
     * @param dataset  the parent dataset
     * @param identifiers the identifiers in the subset as an array
     */
    public DatasetSubset(Dataset dataset, int... identifiers) {
        this( 0,dataset.baseDataSet(), identifiers);
        recalculateWeight();
    }

    public void recalculateWeight() {
        // Process identifier list
        for (int i = 0; i < identifiers.length; ++i) {
            // Find identifier and data point
            int identifier = identifiers[i];
            DataPoint dataPoint = baseDataset.dataPoint(identifier);

            // Check that data point is legal
            if (dataPoint == null) {
                throw new IndexOutOfBoundsException("Cannot access data point with " +
                        "identifier " + identifier + " in data set " + baseDataset);
            }

            // Add data point to data subset
            totalWeight += dataPoint.weight();
        }
    }

    @Override
    public int dimensionality() {
        return baseDataset.dimensionality();
    }


    @Override
    public int size() {
        return identifiers.length;
    }

    @Override
    public double weight() {
        return totalWeight;
    }

    @Override
    public DataPoint dataPoint(int identifier) {
        return baseDataset.dataPoint(identifier);
    }

    @Override
    public Dataset intersection(Dataset otherDataSet) {
        return intersection(this, otherDataSet);
    }

    @Override
    public Dataset difference(Dataset otherDataSet) {
        return difference(this, otherDataSet);
    }

    @Override
    public Dataset union(Dataset otherDataSet) {
        return union(this, otherDataSet);
    }

    @Override
    public DatasetRaw baseDataSet() {
        return baseDataset;
    }

    @Override
    public int append(DataPoint dataPoint) {
        throw new UnsupportedOperationException("Not supported yet.");
    }

    @Override
    public void removeID(int identifier) {
        throw new UnsupportedOperationException("Not supported yet.");
    }

    @Override
    public void trimToSize() {
    }

    @Override
    public DatasetIterator iterator() {
        return new DataSubsetIterator();
    }


    /**
     * The intersection between two data sets.
     * @param dataset1 the first data set
     * @param dataset2 the second data set
     * @return a data set with their intersection
     */
    static Dataset intersection(Dataset dataset1, Dataset dataset2) {
        // Check that the data sets have the same base data set
        Dataset base = dataset1.baseDataSet();
        if (base != dataset2.baseDataSet())
            throw new IllegalArgumentException("the datasets have different base datasets");

        // Create new list of identifiers in intersection
        List<Integer> intersectionList = new ArrayList<Integer>();

        // Iterate through the two data sets in order
        DatasetIterator iterator1 = dataset1.iterator();
        DatasetIterator iterator2 = dataset2.iterator();
        int identifier1 = -1;
        int identifier2 = -1;
        boolean finished = false;
        while (! finished) {
            // We are finished unless we can proceed with one of the iterators
            finished = true;

            // Skip forward in iterator1 until we reach identifier2
            if (identifier1 <= identifier2 && iterator1.hasNext()) {
                iterator1.skipUntil(identifier2);
                if (! iterator1.hasNext())
                    break;
                identifier1 = iterator1.next();
                finished = false;
            }

            // Skip forward in iterator2 until we reach identifier1
            if (identifier2 < identifier1 && iterator2.hasNext()) {
                iterator2.skipUntil(identifier1);
                if (! iterator2.hasNext())
                    break;
                identifier2 = iterator2.next();
                finished = false;
            }

            // Save identifiers in intersection if they are equal
            if (identifier1 == identifier2 && ! finished)
                intersectionList.add(identifier1);
        }
        
        // Create intersection data set
        return new DatasetSubset(base, intersectionList);
    }

    /**
     * The difference between two data sets. This is the data set consisting of
     * all data points in the first data set that are not contained in the second
     * data set.
     * @param dataset1 the first data set
     * @param dataset2 the second data set
     * @return a data set with their difference
     */
    static Dataset difference(Dataset dataset1, Dataset dataset2) {
        // Check that the data sets have the same base data set
        Dataset base = dataset1.baseDataSet();
        if (base != dataset2.baseDataSet())
            throw new IllegalArgumentException("the datasets have different base datasets");

        // Create new list of identifiers in intersection
        List<Integer> differenceList = new ArrayList<Integer>();

        // Iterate through the two data sets in order
        DatasetIterator iterator1 = dataset1.iterator();
        DatasetIterator iterator2 = dataset2.iterator();
        int identifier1 = -1;
        int identifier2 = -1;
        while (iterator1.hasNext()) {
            // Find next data point in dataset1
            identifier1 = iterator1.next();

            // Find first identifier in dataset2 that is >= identifier1
            if (identifier2 < identifier1 && iterator2.hasNext()) {
                iterator2.skipUntil(identifier1);
                if (iterator2.hasNext())
                    identifier2 = iterator2.next();
            }

            // Is identifier from dataset1 contained in dataset2?
            if (identifier1 != identifier2) {
                differenceList.add(identifier1);
            }
        }

        // Create intersection data set
        return new DatasetSubset(base, differenceList);
    }

    /**
     * The union between two data sets.
     * @param dataset1 the first data set
     * @param dataset2 the second data set
     * @return a data set with their union
     */
    static Dataset union(Dataset dataset1, Dataset dataset2) {
        // Check that the data sets have the same base data set
        Dataset base = dataset1.baseDataSet();
        if (base != dataset2.baseDataSet())
            throw new IllegalArgumentException("the datasets have different base datasets");

        // Create new list of identifiers in intersection
        List<Integer> unionList = new ArrayList<Integer>(Math.max(dataset1.size(), dataset2.size()));

        // Iterate through the two data sets in order
        DatasetIterator iterator1 = dataset1.iterator();
        DatasetIterator iterator2 = dataset2.iterator();
        int identifier1 = -1;
        int identifier2 = -1;
        int last = -1;
        boolean finished = false;
        while (! finished) {
            // Finished unless we advance an iterator
            finished = true;

            // Advance iterator1
            if (identifier1 <= last && iterator1.hasNext()) {
                identifier1 = iterator1.next();
                finished = false;
            }

            // Advance iterator2
            if (identifier2 <= last && iterator2.hasNext()) {
                identifier2 = iterator2.next();
                finished = false;
            }

            // Find next in union
            int next = (identifier1 <= last) ? identifier2 :
                (identifier2 <= last) ? identifier1 : Math.min(identifier1, identifier2);

            if (next > last) {
                unionList.add(next);
                last = next;
                finished = false;
            }
        }

        // Create union data set
        return new DatasetSubset(base, unionList);
    }

    @Override
    public DatasetRaw emptyDataset() {
        return baseDataset.emptyDataset();
    }
 
    public class DataSubsetIterator implements DatasetIterator {
        int next = 0;
        int lastskip = 0;

        @Override
        public boolean hasNext() {
            return next < identifiers.length;
        }

        @Override
        public Integer next() {
            // Return next identifier if it exists
            if (hasNext())
                return identifiers[next++];

            // Throw exception if no next element exists
            throw new NoSuchElementException("Cannot iterate beyond position " + next);
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException("DataSubsets do not support element removal");
        }

        private boolean thresholdExceeded(int threshold, int position) {
            // Check whether we have reached end of array
            if (position >= identifiers.length)
                return true;

            // Check whether the threshold has been exceeded
            return identifiers[position] >= threshold;
        }


        @Override
        public void skipUntil(int threshold) {
            // The implementation first checks skips 1b, 11b, 111b, 1111b, etc.
            // (in binary notation). When these skips become too big, we revisit the
            // bits in backwards order, setting them to 0 as appropriate. Ie,
            // after realizing that skip 1111b is too large, we check whether
            // skip 1011b is too large. If it is, we move to the next lower bit and
            // try 1001b; otherwise, we keep the bit and move to the next lower bit
            // by trying 1101b, until there are no more lower bits to explore.
            // The implementation requires 2*n comparisons, where n is the number
            // of significant bits in skip.
            int skip = 0;
            int nextbit = 1;
            
            // Move up to the next higher bit, seting it to 1
            while (! thresholdExceeded(threshold, next + skip)) {
                skip |= nextbit;
                nextbit = nextbit << 1;
            }
            nextbit = nextbit >> 2;
            
            // Move down to the next lower bit, setting it to 0 if necessary
            while (nextbit > 0) {
                // Set next bit to 0 if threshold is still exceeded then
                int skipWithZeroBit = skip ^ nextbit;
                if (thresholdExceeded(threshold, next + skipWithZeroBit))
                    skip = skipWithZeroBit;
                
                // Move down to next bit
                nextbit = nextbit >> 1;
            }
            
            // Set next to skip + next
            next += skip;
        }
    }
}
